﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0190_KClosest : IAlgorithm
    {
        // 973. 最接近原点的 K 个点

        // 给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。
        // 这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。
        // 你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。

        // 提示：

        //  1 <= k <= points.length <= 10^4
        //  -10^4 < xi, yi< 10^4

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        Random rand = new Random();
        public int[][] KClosest(int[][] points, int k)
        {
            int n = points.Length;
            RandomSelect(points, 0, n - 1, k);
            return points.Take(k).ToArray();
        }

        public void RandomSelect(int[][] points, int left, int right, int k)
        {
            int pivotId = left + rand.Next(right - left + 1);
            int pivot = points[pivotId][0] * points[pivotId][0] + points[pivotId][1] * points[pivotId][1];
            Swap(points, right, pivotId);
            int i = left - 1;
            for (int j = left; j < right; ++j)
            {
                int dist = points[j][0] * points[j][0] + points[j][1] * points[j][1];
                if (dist <= pivot)
                {
                    ++i;
                    Swap(points, i, j);
                }
            }
            ++i;
            Swap(points, i, right);
            // [left, i-1] 都小于等于 pivot, [i+1, right] 都大于 pivot
            if (k < i - left + 1)
            {
                RandomSelect(points, left, i - 1, k);
            }
            else if (k > i - left + 1)
            {
                RandomSelect(points, i + 1, right, k - (i - left + 1));
            }
        }

        public void Swap(int[][] points, int index1, int index2)
        {
            int[] temp = points[index1];
            points[index1] = points[index2];
            points[index2] = temp;
        }
    }
}
